The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure. Unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in the present disclosure and are not admitted to be prior art by inclusion in this section.
Computer software may be created in multiple stages. A computer programmer may write human-readable source code (e.g., in C, C++, JAVA® programming language). This source code may then be transformed by a compiler or an interpreter (hereinafter, simply “compiler”) into lower-level instructions, such as assembly language instructions and/or machine code instructions, that may be executed by one or more processors (e.g., by a processor core of a multi-core processor).
During compilation or interpretation (hereinafter, simply “compilation”), assembly or machine instructions may be reordered, or “optimized,” so that they may be executed more quickly and/or efficiently at runtime. However, it may be difficult to determine whether memory instructions such as load and store will access the same memory location (known as “memory aliasing”) at runtime. Accordingly, a compiler or interpreter may optimize instructions as if there will be no memory aliasing among these instructions, while preserving the instructions' original execution order (e.g., using annotations or with additional instructions) in case memory aliasing arises at runtime.
A processor may be equipped with memory disambiguation circuitry to perform speculative memory optimization. At runtime, if the memory disambiguation circuitry detects memory aliasing, it may trigger a memory aliasing exception. Optimized instructions may be stored in an atomic region so that, in the event of a memory aliasing exception, the whole atomic region may be rolled back. Then, original or less-optimized instructions may be executed instead.
Rotation-based memory disambiguation circuitry may detect memory aliasing based on an original execution order of a sequence of instructions. After execution of a memory instruction, the memory address accessed by the instruction may be stored in an alias register queue at a location corresponding to the instruction's location in the original execution order of the sequence of instructions (which as noted above was preserved during compilation). The memory disambiguation circuitry then may compare that memory address with memory addresses accessed by instructions contained in “later” alias register entries (e.g., entries with greater indices) to detect memory aliasing.
Rotation-based memory disambiguation may perform well for instruction scheduling in sequential computer programs. However, it may not perform as well for instruction optimizations in more complex situations. For example, when handling speculative load or store eliminations, memory disambiguation circuitry may unnecessarily alias check memory accessed by instructions that are not actually reordered during optimization. Handling branching programs also may be difficult because there is no original program execution order between memory instructions in different branches, and yet, memory addresses accessed by these instructions may still be assigned to alias registers. With loops, sequential release of alias register entries through iterations (also referred to as “rotations”) of the loop may restrict optimization of loop instructions to a sliding window bounded by the size of the alias register queue.